// 给你一个整数数组 nums 和一个整数 target 。

// 向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：

// 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
// 返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

//  

// 示例 1：

// 输入：nums = [1,1,1,1,1], target = 3
// 输出：5
// 解释：一共有 5 种方法让最终目标和为 3 。
// -1 + 1 + 1 + 1 + 1 = 3
// +1 - 1 + 1 + 1 + 1 = 3
// +1 + 1 - 1 + 1 + 1 = 3
// +1 + 1 + 1 - 1 + 1 = 3
// +1 + 1 + 1 + 1 - 1 = 3
//方法一，枚举  直接计算所有的情况
public class Solution {
    int count = 0;
    public int findTargetSumWays(int[] nums, int S) {
        calculate(nums, 0, 0, S);
        return count;
    }
    public void calculate(int[] nums, int i, int sum, int S) {
        if (i == nums.length) {
            if (sum == S)
                count++;
        } else {
            calculate(nums, i + 1, sum + nums[i], S);
            calculate(nums, i + 1, sum - nums[i], S);
        }
    }
}
//方法二：背包
public class Solution {
    public int findTargetSumWays(int[] nums, int S) {
        int sum = 0;
        int len = nums.length;
        for(int i=0;i<len;i++)
        {
            sum+=nums[i];
        }
        if(sum<Math.abs(S))
            return 0;
        int total = sum*2+1;
        int[][]dp = new int[len][total];

        dp[0][nums[0]+sum] = 1;
        dp[0][sum-nums[0]] +=1;
        for(int i =1;i<len;i++)
            for(int j = -sum;j<=sum;j++)
            {
                if(j+nums[i]+sum>=total)
                {
                    dp[i][j+sum] = dp[i-1][j-nums[i]+sum];
                }
                else if(j+sum-nums[i]<0)
                {
                    dp[i][j+sum] =  dp[i-1][j+nums[i]+sum];
                }
                else{
                    dp[i][j+sum] = dp[i-1][j-nums[i]+sum]+dp[i-1][j+nums[i]+sum];
                }
            }
        return dp[len-1][sum+S];
    }
}

